package com.cheung.leetcode.stack;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Stack;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.stack
 * @Author :  cheungming
 * @CreateTime : 2024-06-20 08:48:00
 * @Description : 下一个更大元素 II
 * @Version : 1.0
 */
public class Code503Test {

    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] res = new int[length];
        Arrays.fill(res, -1);
        if (length == 0) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length * 2; i++) {
            // 栈不为空，并且栈顶元素小于当前元素，出栈，并记录下一个更大元素
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % length]) {
                res[stack.pop()] = nums[i % length];
            }
            // 栈为空或者栈顶元素大于当前元素，入栈
            stack.push(i % length);
        }

        return res;
    }

    @Test
    public void test1() {
        assert Arrays.equals(nextGreaterElements(new int[]{1, 2, 1}), new int[]{2, -1, 2});
    }

    @Test
    public void test2() {
        assert Arrays.equals(nextGreaterElements(new int[]{1, 2, 3, 4, 3}), new int[]{2, 3, 4, -1, 4});
    }
}
